class Solution
{
public:
    int uniquePaths(int m, int n)
    {
        vector<vector<int>> memo(m + 1, vector<int>(n + 1));
        memo[1][1] = 1;
        return dfs(memo, m, n);
    }

    int dfs(vector<vector<int>>& memo, int r, int c)
    {
        if (memo[r][c] != 0)
            return memo[r][c];
        if (r == 0 || c == 0)
            return 0;
        memo[r][c] = dfs(memo, r - 1, c) + dfs(memo, r, c - 1);
        return memo[r][c];
    }
};